package LeetCode.Greedy;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author : LdLtd
 * @Date : 2023/7/25
 * @Description:2208. 将数组和减半的最少操作次数
 */
public class minimum_operations_to_halve_array_sum {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int [] nums = {5,19,8,1};
        System.out.println(solution.halveArray(nums));
    }
    /*优先队列+贪心，每次找最大的数*/
    static class Solution {
        public int halveArray(int[] nums) {
            PriorityQueue<Double> pq = new PriorityQueue<Double>((a, b) -> b.compareTo(a));
//            double sum = Arrays.stream(nums).sum()*0.5;
            double sum2 = Arrays.stream(nums).asDoubleStream().sum();
//            System.out.println(sum);
            double sum=0,t=0.0;
            int count=0;
            for (int num:nums){
                sum+=num;
                pq.offer((double) num);
            }
            while(t<sum/2){
                double x=pq.poll();
                t+=x/2;
                pq.offer(x/2);
                count++;
            }
            return count;


        }
    }
}
